package com.demo.work;

import java.io.*;
import java.util.*;

/**
 * @program: ssm_demo
 * @author: Mr.Zhuo
 * @create: 2022-04-11 23:05
 **/
public class BinarySearchTree {

    private class Node {
        int data; // 数据域
        Node left; // 左子树
        Node right; // 右子树
    }

    private Node root; // 二叉排序树根节点



    /**
     *   主要想模仿  mysql的索引，底层用的B+Tree
     *   每次查找都是需要比较，一次比较进行筛选出来一半的数据
     *   功能可能有些欠缺  部分ascll值可能会相等  正在思考用什么数据来替代
     *   但是基本查找功能已实现，已存在的数据都可以查找
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        // 读取文件
        String filePath = "d:\\baidu.txt";

        String readTxt = readTxt(filePath);

        // 取得每个单个词
        String[] strings = readTxt.split(":");

        // 定义一个每个单个词对应的ascll数组
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (String string : strings) {
            Integer sum = 0;
            for (Integer i = 0; i < string.length(); i++) {
                sum += string.charAt(i) - 0;
            }
            arrayList.add(sum);
        }

        // 二叉查找树
        BinarySearchTree tree = new BinarySearchTree();

        // 然后进行数据插入
        for (Integer integer : arrayList) {
            tree.insert(integer);
        }

        System.out.println("请输入要查找的词：");
        Scanner scanner = new Scanner(System.in);

        String nextLine = scanner.next();

        // 获取输入的词的ascll值
        Integer num = 0;
        for (int i = 0; i < nextLine.length(); i++) {
            num += nextLine.charAt(i) - 0;
        }

        Node node = tree.find(num);

        // 进行条件判断
        if (node!=null){
            System.out.println("存在");
        }else {
            System.out.println("不存在");
        }
    }


    /**
     * 创建二叉排序树
     *
     * @param key
     */
    public void insert(int key) {
        Node p = new Node(); // 要插入的结点
        p.data = key;

        if (root == null) {
            root = p;
        } else {
            Node parent = new Node();
            Node current = root; // 当前结点
            while (true) {
                parent = current;
                if (key > current.data) {
                    current = current.right;
                    if (current == null) {
                        parent.right = p;
                        return;
                    }
                } else { // 这里不考虑key出现和二叉排序树结点中的值相等的情况
                    current = current.left;
                    if (current == null) {
                        parent.left = p;
                        return;
                    }
                }

            }
        }
    }

    /**
     * 按照关键值，查找结点。
     *
     * @param key
     * @return
     */
    public Node find(int key) {
        Node current = root;
        while (current.data != key) {
            if (key > current.data) {
                current = current.right;
            } else {
                current = current.left;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }


    /**
     * 中序遍历     左、根、右
     *
     * @param root
     */
    public void inOrder(Node root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + " | ");
            inOrder(root.right);
        }
    }




    // 读取文件
    public static String readTxt(String path) throws Exception {
        StringBuilder strb = new StringBuilder("");

        // 获取文件流
        InputStream is = new FileInputStream(new File(path));

        InputStreamReader isr = new InputStreamReader(is, getCode(path));

        BufferedReader br = new BufferedReader(isr);

        String str = "";

        while (null != (str = br.readLine())) {
            strb.append(str);

            strb.append(":");
        }

        br.close();

        return strb.toString();

    }

    // 获取编码格式 gb2312,UTF-16,UTF-8,Unicode,UTF-8
    public static String getCode(String path) throws Exception {
        InputStream inputStream = new FileInputStream(path);

        byte[] head = new byte[3];

        inputStream.read(head);

        String code = "UTF-8"; // 或GBK

        if (head[0] == -1 && head[1] == -2)

            code = "UTF-8";

        else if (head[0] == -2 && head[1] == -1)

            code = "UTF-8";

        else if (head[0] == -17 && head[1] == -69 && head[2] == -65)

            code = "UTF-8";

        inputStream.close();

        return code;

    }


}
